{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一组非负整数 <code>nums</code>，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。</p>\n",
    "\n",
    "<p><strong>注意：</strong>输出结果可能非常大，所以你需要返回一个字符串而不是整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入<code>：</code></strong><code>nums = [10,2]</code>\n",
    "<strong>输出：</strong><code>\"210\"</code></pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入<code>：</code></strong><code>nums = [3,30,34,5,9]</code>\n",
    "<strong>输出：</strong><code>\"9534330\"</code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-number](https://leetcode.cn/problems/largest-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-number](https://leetcode.cn/problems/largest-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,2]', '[3,30,34,5,9]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "\n",
    "def compare ( a, b ):\n",
    "  x = a + b\n",
    "  y = b + a\n",
    "\n",
    "  if x < y:\n",
    "    return -1\n",
    "  elif x > y:\n",
    "    return 1\n",
    "  else:\n",
    "    return 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "  def largestNumber(self, nums):\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :rtype: str\n",
    "    \"\"\"\n",
    "    if len( nums ) == 0:\n",
    "      return ''\n",
    "\n",
    "    snums = [ str( n ) for n in nums ]\n",
    "    snums.sort( key = cmp_to_key( compare ), reverse = True )\n",
    "    ans = ''.join( s for s in snums )\n",
    "\n",
    "    return ans if set( ans ) != {'0'} else '0'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res=\"\"\n",
    "        nums=self.sort(nums)\n",
    "      \n",
    "        for i in range(len(nums)):\n",
    "            res=res+str(nums[i])\n",
    "        \n",
    "        if res[0]=='0':\n",
    "            return '0'\n",
    "        \n",
    "        return res\n",
    "    \n",
    "    def helper(self,a,b):\n",
    "        stra,strb=str(a),str(b)\n",
    "        \n",
    "        if int(stra+strb)>int(strb+stra):\n",
    "            return a\n",
    "        else:\n",
    "            return b\n",
    "        \n",
    "    def sort(self,nums):\n",
    "        if not nums:\n",
    "            return []\n",
    "        \n",
    "        if len(nums)==1:\n",
    "            return nums\n",
    "        \n",
    "        n=int(len(nums)/2)\n",
    "        a,b=nums[0:n],nums[n:]\n",
    "        a=self.sort(a)\n",
    "        b=self.sort(b)\n",
    "        return self.merge(a,b)\n",
    "        \n",
    "    def merge(self,num1,num2):\n",
    "        if (not num1) and (not num2):\n",
    "            return []\n",
    "        if not num1:\n",
    "            return num2\n",
    "        if not num2:\n",
    "            return num1\n",
    "        \n",
    "        res=[]\n",
    "        \n",
    "        i,j=0,0\n",
    "        \n",
    "        while i<len(num1) and j<len(num2):\n",
    "            if self.helper(num1[i],num2[j])==num1[i]:\n",
    "                res.append(num1[i])\n",
    "                i+=1\n",
    "            else:\n",
    "                res.append(num2[j])\n",
    "                j+=1\n",
    "                \n",
    "        if i<len(num1):\n",
    "            for k in range(i,len(num1)):\n",
    "                res.append(num1[k])\n",
    "                \n",
    "        if j<len(num2):\n",
    "            for k in range(j,len(num2)):\n",
    "                res.append(num2[k])\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: 'List[int]') -> 'str':\n",
    "        def num_to_digits(num):\n",
    "            if num == 0:\n",
    "                return [0]\n",
    "            digits = []\n",
    "            while num:\n",
    "                digits.insert(0, num % 10)\n",
    "                num = num // 10\n",
    "            return digits\n",
    "        \n",
    "        def compare(a, b):\n",
    "            a, b = num_to_digits(a), num_to_digits(b)\n",
    "            la, lb = len(a), len(b)\n",
    "            for i in range(la + lb):\n",
    "                if a[i % la] > b[i % lb]:\n",
    "                    return -1\n",
    "                elif a[i % la] < b[i % lb]:\n",
    "                    return 1\n",
    "            return 0\n",
    "        \n",
    "        nums = sorted(nums, key=functools.cmp_to_key(compare))\n",
    "        ret = ''.join(map(str, nums)).lstrip('0')\n",
    "        if not ret:\n",
    "            return '0'\n",
    "        else:\n",
    "            return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "class Solution:\n",
    "    def mycmp(self,x, y):\n",
    "        if x + y > y + x:\n",
    "            return 1\n",
    "        else:\n",
    "            return -1\n",
    "    def largestNumber(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        strs = [str(num) for num in nums]\n",
    "        strs.sort(key = cmp_to_key(self.mycmp), reverse = True)\n",
    "        return ''.join(strs).lstrip('0') or '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        import functools\n",
    "        def cmp(num1,num2):\n",
    "            n1 = len(num1);n2 = len(num2)\n",
    "            if n1 == n2:\n",
    "                if num1 < num2:\n",
    "                    return -1\n",
    "                else:\n",
    "                    return 1\n",
    "            if num1 + num2 < num2 + num1:\n",
    "                return -1\n",
    "            else:\n",
    "                return 1\n",
    "\n",
    "        nums = [str(num) for num in nums]\n",
    "        nums = sorted(nums,key=functools.cmp_to_key(cmp),reverse=True)\n",
    "        res = \"\".join(nums)\n",
    "        i = 0\n",
    "        while i < len(res)-1 and res[i] == '0':\n",
    "            i += 1\n",
    "        return res[i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "def compare(x, y):\n",
    "    if x==y:\n",
    "        return 0\n",
    "    s1, s2 = str(x), str(y)\n",
    "    if int(s1+s2)>int(s2+s1):\n",
    "        return -1\n",
    "    else:\n",
    "        return 1\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        if sum(nums)==0:\n",
    "            return '0'\n",
    "        nums = sorted(nums, key=cmp_to_key(compare))\n",
    "        return ''.join([str(num) for num in nums])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        len1=len(nums)\n",
    "        if len1<=1:\n",
    "            print(str(nums))\n",
    "        for i in range(len1):\n",
    "            for j in range(0,len1-i-1):\n",
    "                if str(nums[j])+str(nums[j+1])<str(nums[j+1])+str(nums[j]):\n",
    "                    tem=nums[j]\n",
    "                    nums[j]=nums[j+1]\n",
    "                    nums[j+1]=tem\n",
    "        ans=\"\"\n",
    "        for i in range(len1):\n",
    "            ans+=str(nums[i])\n",
    "        if ans[0]=='0':\n",
    "            return '0'\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums) - i - 1):\n",
    "                if str(nums[j]) + str(nums[j + 1]) > str(nums[j + 1]) + str(nums[j]):\n",
    "                    nums[j], nums[j + 1] = nums[j + 1], nums[j]\n",
    "        s = ''\n",
    "        if nums[-1] == 0:\n",
    "            return('0')\n",
    "        for i in nums:\n",
    "            s = str(i) + s\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        res = ''\n",
    "        for i in range(len(nums) - 1):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                if int(str(nums[i]) + str(nums[j])) < int(str(nums[j]) + str(nums[i])):\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\n",
    "        for num in nums:\n",
    "            res += str(num)\n",
    "        return '0' if res[0] == '0' else res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "\n",
    "def func(str1, str2):\n",
    "    if str1 + str2 < str2 + str1:\n",
    "        return 1\n",
    "    elif str1 + str2 == str2 + str1:\n",
    "        return 0\n",
    "    else:\n",
    "        return -1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # def largestNumber(self, nums: List[int]) -> str:\n",
    "    def largestNumber(self, nums: list) -> str:\n",
    "        res = ''.join(sorted(map(str, nums), key=functools.cmp_to_key(func)))\n",
    "        return '0' if res[0] == '0' else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        s = \"\"\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if str(nums[i])+str(nums[j]) < str(nums[j])+str(nums[i]):\n",
    "                    nums[i],nums[j] = nums[j],nums[i]\n",
    "        print(nums)\n",
    "        for k in nums:\n",
    "            s = s + str(k)\n",
    "        return str(int(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        # if not nums:\n",
    "        #     return \"\"\n",
    "        # elif len(nums) == 1:\n",
    "        #     return str(nums[0])\n",
    "\n",
    "        # nums_str = [str(i) for i in nums]\n",
    "        # nums_str.sort()\n",
    "        # for i in range(len(nums_str)-1):\n",
    "        #     for j in range(i+1,len(nums_str)):\n",
    "        #         if nums_str[i] != nums_str[j]:\n",
    "        #             if nums_str[i]+nums_str[j] < nums_str[j]+nums_str[i]:\n",
    "        #                 nums_str[i], nums_str[j] = nums_str[j], nums_str[i]\n",
    "        # res = \"\".join(nums_str)\n",
    "        # if set(res) == {\"0\"}:\n",
    "        #     return \"0\"\n",
    "        # return res\n",
    "        result = ''.join(sorted(map(str, nums), key=Tool))\n",
    "        return \"0\" if result[0] == '0' else result\n",
    "\n",
    "class Tool(str):\n",
    "    def __lt__(x, y):\n",
    "        return x+y>y+x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        length=len(nums)\n",
    "        i=length\n",
    "        while i>0:\n",
    "            for j in range(i-1):\n",
    "                a=nums[j]\n",
    "                b=nums[j+1]\n",
    "                ab=int(str(a)+str(b))\n",
    "                ba=int(str(b)+str(a))\n",
    "                if ba>ab:\n",
    "                    nums[j],nums[j+1]=nums[j+1],nums[j]\n",
    "            i-=1\n",
    "        res=''\n",
    "        for n in nums:\n",
    "            if res==\"\" and n==0:\n",
    "                continue\n",
    "            res+=str(n)\n",
    "        if res=='':\n",
    "            return '0'\n",
    "        else:\n",
    "            return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "\n",
    "        def compare(num1, num2):\n",
    "            if int(num1 + num2) > int(num2 + num1):\n",
    "                return -1\n",
    "            else:\n",
    "                return 1\n",
    "\n",
    "        nums = list(map(str, nums))\n",
    "        nums.sort(key=functools.cmp_to_key(compare))\n",
    "        res = \"\"\n",
    "        for each in nums:\n",
    "            res += each\n",
    "        cur = 0\n",
    "        while cur < len(res) - 1 and res[cur] == '0':\n",
    "            cur += 1\n",
    "        return res[cur: ]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        from functools import cmp_to_key\n",
    "        def helper(x, y):\n",
    "            if x + y > y + x:\n",
    "                return -1\n",
    "            elif x + y < y + x:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        return \"\".join(sorted(map(str, nums), key=cmp_to_key(helper))).lstrip(\"0\") or \"0\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def largestNumber(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if any(nums):\n",
    "            from functools import cmp_to_key\n",
    "            nums = sorted([str(x) for x in nums], key=cmp_to_key(lambda x, y: int(x + y) - int(y + x)), reverse=True)\n",
    "            return ''.join(nums)\n",
    "        return '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        arr = [str(num) for num in nums]\n",
    "        def lq(s1, s2):\n",
    "            if s1+s2 > s2+s1:\n",
    "                return False\n",
    "            return True\n",
    "        def quicksort(l, r):\n",
    "            if l >= r:\n",
    "                return\n",
    "            ind = l+1\n",
    "            for i in range(l+1, r+1):\n",
    "                if lq(arr[i], arr[l]):\n",
    "                    arr[i], arr[ind] = arr[ind], arr[i]\n",
    "                    ind += 1\n",
    "            arr[ind-1], arr[l] = arr[l], arr[ind-1]\n",
    "            quicksort(l, ind-2)\n",
    "            quicksort(ind, r)\n",
    "        quicksort(0, len(arr)-1)\n",
    "        res = ''.join(reversed(arr))\n",
    "        if res[0] == '0':\n",
    "            return '0'\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        d=dict()\t\t\n",
    "        def fl(l):\n",
    "            if tuple(l) in d:return d[tuple(l)]\n",
    "            if len(l)==1:return str(l[0])\n",
    "            ms='0'\n",
    "            for pos in range(len(l)):\n",
    "                n0=l[pos]\n",
    "                if str(n0)>=ms[:len(str(n0))]:\n",
    "                    m=fl(l[:pos]+l[pos+1:])\n",
    "                    if str(n0)+m>ms:\n",
    "                        ms=str(n0)+m\n",
    "            d[tuple(l)]=ms\n",
    "            return(ms)\n",
    "        nums.sort(key=str,reverse=True)\n",
    "        r=fl(nums)\n",
    "        if r.startswith('0'):r='0'\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        from functools import cmp_to_key\n",
    "        nums_str = list(map(str, nums))\n",
    "        k = cmp_to_key(lambda x,y: int(y+x)-int(x+y))\n",
    "        nums_str.sort(key=k)\n",
    "\n",
    "        if nums_str[0] == '0':\n",
    "            return '0'\n",
    "        return ''.join(nums_str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        n=len(nums)\n",
    "        numlist=list(map(str,nums))\n",
    "        for i in range(n):\n",
    "            for j in range(n-1,i,-1):\n",
    "                if numlist[i] + numlist[j] < numlist[j] + numlist[i]:\n",
    "                    numlist[i],numlist[j]=numlist[j],numlist[i]\n",
    "        if numlist[0]==\"0\":\n",
    "            return \"0\"\n",
    "        return ''.join(numlist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        nums = list(map(str, nums))\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[i]+nums[j]>nums[j]+nums[i]:\n",
    "                    mid = nums[i]\n",
    "                    nums[i] = nums[j]\n",
    "                    nums[j] = mid\n",
    "        s = ''.join(nums)\n",
    "        s = str(int(s))\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        def compare(x, y): return int(y+x) - int(x+y)\n",
    "        nums = sorted(map(str, nums), key=cmp_to_key(compare))\n",
    "        return \"0\" if nums[0]==\"0\" else \"\".join(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        #print(nums)\n",
    "        if not any(nums):\n",
    "            return '0'\n",
    "\n",
    "        str_nums = [str(i) for i in nums]\n",
    "        print(str_nums)\n",
    "        def cmp_by_alpha(a,b):\n",
    "            if a+b > b+a:\n",
    "                return -1\n",
    "            elif a+b < b+a:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        str_nums.sort(key = functools.cmp_to_key(cmp_by_alpha))\n",
    "        print(str_nums)\n",
    "        return ''.join(str_nums)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        def quick_sort(l, r):\n",
    "            if l >= r: return\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while i < j and nums[j] + nums[l] <= nums[l] + nums[j]: j -= 1\n",
    "                while i < j and nums[i] + nums[l] >= nums[l] + nums[i]: i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "            nums[i], nums[l] = nums[l], nums[i]\n",
    "            quick_sort(l, i-1)\n",
    "            quick_sort(i+1, r)\n",
    "\n",
    "        nums = list(map(str, nums))\n",
    "        quick_sort(0, len(nums)-1)\n",
    "        return ''.join(nums) if nums[0] != '0' else '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        print(nums)\n",
    "        sign0 = True\n",
    "        for i in range(len(nums)):\n",
    "            if(nums[i] != 0):\n",
    "                sign0 = False\n",
    "                break\n",
    "        if(sign0):\n",
    "            return \"0\"\n",
    "\n",
    "        def cmp_num(y, x):\n",
    "            xs = str(x)    # 23\n",
    "            ys = str(y)    # 231\n",
    "            lx = len(xs)\n",
    "            ly = len(ys)\n",
    "            xxs = xs\n",
    "            yys = ys\n",
    "            print(xs, ys, lx,ly)\n",
    "            if(lx < ly):\n",
    "                for i in range(ly - lx):\n",
    "                    idx = (i % lx)\n",
    "                    xxs += xs[idx]\n",
    "            if(ly < lx):\n",
    "                for i in range(lx - ly):\n",
    "                    idx = (i % ly)\n",
    "                    yys += ys[idx]\n",
    "\n",
    "            l = len(xxs)\n",
    "            for i in range(l):\n",
    "                if(xxs[i] > yys[i]):\n",
    "                    return 1\n",
    "                elif((xxs[i] < yys[i])):\n",
    "                    return -1\n",
    "            if(lx < ly):\n",
    "                print(\"111  xs:%s  ys:%s\"%(xs,ys[ly-lx: ly]))\n",
    "                if(xs > ys[ly-lx: ly]):\n",
    "                    return -1\n",
    "                elif(xs < ys[ly-lx: ly]):\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            elif(lx > ly):\n",
    "                print(\"222  xs:%s  ys:%s\"%(xs[lx-ly: lx],ys))\n",
    "                if(xs[lx-ly: lx] > ys):\n",
    "                    return -1\n",
    "                elif(xs[lx-ly: lx] > ys):\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            return 0\n",
    "\n",
    "        nums.sort(key = functools.cmp_to_key(cmp_num))\n",
    "        return \"\".join(map(str, nums))\n",
    "\n",
    "s = Solution()\n",
    "s.largestNumber([432,43243])\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        n=len(nums)\n",
    "        nums=list(map(str,nums))\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if nums[i]+nums[j]<nums[j]+nums[i]:\n",
    "                    nums[i],nums[j]=nums[j],nums[i]\n",
    "        \n",
    "        return str(int(\"\".join(nums)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        res = list(map(str, nums))\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if int(res[i]+res[j])<int(res[j]+res[i]):\n",
    "                    res[i], res[j] = res[j], res[i]\n",
    " \n",
    "        return str(int(''.join(res)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestNumber(self, nums: List[int]) -> str:\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if str(nums[i])+str(nums[j])<str(nums[j])+str(nums[i]):\n",
    "                    nums[i],nums[j] = nums[j],nums[i]\n",
    "        num = [str(n) for n in nums]\n",
    "        if num[0] == '0':\n",
    "            return \"0\"\n",
    "        else:\n",
    "            return \"\".join(num)\n",
    "\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
